概率数据结构

codeskills, coding, doc, julia    
  1. 概率数据结构
    1. 散列 Hashing
      1. 加密散列函数
      2. 非加密散列函数
      3. 散列表
    2. 成员查询 Membership querying
      1. 布隆过滤器 Bloom Filter
      2. 计数布隆过滤器 Counting Bloom Filter
      3. 商数过滤器 Quotient Filter
      4. 布谷过滤器 Cuckoo Filter
    3. 基数 Cardinatlity
      1. 线性计数 Linear counting
      2. 概率计数 probabilistic counting
      3. LogLog
      4. HyperLogLog
      5. HyperLogLog
    4. 频率 Frequency
      1. 多数投票算法 Majority algorithm
      2. 频繁算法 Frequent
      3. Count Sketch
      4. Count-Min Sketch
    5. 排序 Rank
      1. 随机采样 Random sampling
      2. q-摘要 q-digest
      3. t-摘要 t-digest
    6. 相似性 Similarity
      1. 局部敏感散列 LSH
      2. MinHash
      3. SimHash

概率数据结构

参考书目 本文主要参考《面向大数据应用的概率数据结构与算法》中的内容。

散列 Hashing

  • 生成固定大小的标识符(hash)

  • 散列碰撞(hash collisions): 两个不同的数据块具有相同散列值

加密散列函数

加密散列函数为了保证抗碰撞性, 所以牺牲了一部分性能, 效率低于非加密散列函数: 加密散列速度约540MiB/s, 非加密约2500MiB/s。

  • 消息-摘要算法 (Message–Digest Algorithms) MD5

  • 安全散列算法 (Secure Hash Algorithms) SHA-2(SHA-224, SHA-256, SHA-384, SHA-512等)

  • RadioGatún: 比SHA-2快

非加密散列函数

  • Fowler/Noll/Vo (FNV): 基于素数

  • MurmurHash: 当下最流行的算法, 用于Hadoop, ES, nginx等

  • CityHash与FarmHash: google开发的算法, 依赖于平台。

散列表

负载因子α: 使用的键数量n与表总长m的比值, 是散列表填充程度的度量。

散列表解决碰撞问题主要有两种技术:

  • 封闭寻址: 将碰撞元素存储在辅助数据结构中的相同键下, 最简单

  • 开放寻址: 将碰撞元素存储在首位以外的其他位置, 并提供一种寻址方法

成员查询 Membership querying

  • 确定某个元素是否属于该数据集。

  • 不需要确定的匹配, 只需要只到在不在集合中, 所以可以只存储元素的签名

  • 兼顾存储效率和查询速率

用散列表存储, 容易出现散列碰撞, 且对大数据来说存储压力依然大, 所以需要新的替代算法。

布隆过滤器 Bloom Filter

  • 最简单最知名的成员查询解决方案

  • 常用比特数组来表示元素集合

  • 只支持添加元素和测试元素是否属于集合两种操作

  • 散列函数要尽量相互独立且服从均匀分布

插入元素`x`

  1. 根据散列函数\(h_k\),计算x的散列值: \(j = h_k(x)\) (使用k个散列函数)

  2. 将过滤器(长度为m的比特数组)中对应j位置元素设置为1

伪代码:

julia

for i in 1:k
    j = h_i(x)
    BLOOMFILTER(j) = 1
end

julia
检查元素`y`是否存在

  1. 用构建过滤器的散列函数计算y的散列值: \(j=h_k(y)\)

  2. 判断如果BLOOMFILTER[j] != 1, 则表示元素不存在

  • 如果散列函数\(h_k\)能够在固定时间中算出, 则添加和判断元素的时间为固定常数\(O(k)\), 而不受过滤器长度和元素数目的限制。

  • 高度依赖散列函数, 越均匀, 计算越快的越好。

  • 由于散列碰撞, 判断为不存在的元素一定不存在, 但判断为存在的元素有概率误判。

计算过滤器中不同元素的数量 输入: 长度为m,含k个散列函数的布隆过滤器BloomFilter 输出: 过滤器中不同元素的个数 伪代码:
julia

N = count([ BLOOMFILTER[j]=1 for j in 1:m ])
if N<k then
    return 0
elseif N==k then
    return 1
elseif N==m then
    return m/k
else
    return -(m/k)*ln(1-N/m)
end

julia

估算长度算法背后的原理:

  1. 布隆过滤器的假阳性率P_{fp}可以由公式\(P_{fp} ≈ (1-e^{-kn/m})^k\) 估算,取决于k和m的选择

  2. 过滤器长度由公式\(m = - n*ln(P_{fp})/(ln2)^2\) 估算

  3. 保持误报率不变情况下, 过滤器大小和元素数量呈线性关系: \( m/n = C \), C即为每个元素需要分配的平均存储位数

  4. 由假阳性率公式可以推出, 最优k取值为\( k=(m/n)ln2≈0.7C \), 一般选择向下取整的k取值

\(k\)\(m/n\)\(P_{fp}\)
460.0561
680.0215
8120.00314
11160.000458

布隆过滤器不支持删除操作.

计数布隆过滤器 Counting Bloom Filter

一种支持删除操作的布隆过滤器, 引入一个大小为m的计数器数组\({C_j}^m_{j=1}\), 添加元素时, 增加对应的计数器数值, 且当计数器值为1时才更新比特数组:

julia

for i in 1:k
    j = h_i(x)
    Cj = Cj + 1
    if Cj == 1
        CountingBloomFilter[j] = 1
    end
end

julia

删除元素

  1. 计算散列值

  2. 减少对应计数器的值

  3. 如果计数器值变为0，则复位对应的比特数组位置

计数布隆过滤器的计数器往往要占用4Bt或更多, 所以比布隆过滤器往往要多4倍以上的空间

商数过滤器 Quotient Filter

  • 布隆过滤器(及其变种)的任何操作都需要多次随机访问,所以不适合存储在硬盘上

  • 商数过滤器就没有这个问题, 其数据局部性更好,只需要连续少量硬盘访问

  • 支持元素删除,可以动态调整大小或者合并

  • 空间和时间性能与布隆过滤器相当

实现

  • 给定数据集\(D={x_1, x_2, ..., x_n}\), 商数过滤器通过一个散列函数,对每个元素存储大小为\(p\)比特的指纹,

并利用商法将每个指纹分割为长度为\(q\)比特的最高有效位(商)和长度为\(r\)比特的最低有效位(余数)。fr = f ÷ 2^r; fq = f % 2^r;

  • 使用一个以商fq为索引以余数fr为值的桶来存储指纹, 指纹可以重建为: f=fq * 2^r + fr

  • 每个桶包含三个元比特: is_occupied, is_continuation, is_shifted, 均初始化为0

  • 桶j为某个指纹的规范桶(fq=j)且该指纹存储在桶j中时, is_occupied置为1

  • 余数不是第一个被映射到该桶的余数时, is_continuation置为1

  • 桶中存储的余数的规范桶为其他桶时, is_shifted置为1

布谷过滤器 Cuckoo Filter

基数 Cardinatlity

线性计数 Linear counting

概率计数 probabilistic counting

LogLog

HyperLogLog

HyperLogLog

频率 Frequency

多数投票算法 Majority algorithm

频繁算法 Frequent

Count Sketch

Count-Min Sketch

排序 Rank

随机采样 Random sampling

q-摘要 q-digest

t-摘要 t-digest

相似性 Similarity

局部敏感散列 LSH

MinHash

SimHash